package solution;

import java.util.*;

/**
 * @author zhangmin
 * @create 2021-08-02 20:57
 * 数组部分
 */
public class Solution_1array {

    /*===========================================================================================================================
    * 前缀和 560. 和为 K 的子数组
    * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。
    * */
    //1.前缀和
    public int subarraySum1(int[] nums, int k) {
        int n=nums.length;
        int[] sum=new int[n+1];
        sum[0]=0;
        for (int i = 0; i < n; i++) {
            sum[i+1]=sum[i]+nums[i];
        }
        int res=0;
        for (int i = 1; i <=n ; i++) {
            for (int j = 0; j < i; j++) {
                if (sum[i]-sum[j]==k)
                    res++;
            }
        }
        return res;
    }
    //2.直接记录下有几个 sum[j] 和 sum[i] - k 相等，直接更新结果，就避免了内层的 for 循环。
    public int subarraySum(int[] nums, int k) {
        int n=nums.length;
        // map：前缀和 -> 该前缀和出现的次数
        HashMap<Integer,Integer> preSum=new HashMap<>();
        preSum.put(0,1);
        int res=0;
        int sum=0;
        for (int i = 0; i < n; i++) {
            sum+=nums[i];
            //需要找到sum-k的前缀和的个数
            int sum_j=sum-k;
            if (preSum.containsKey(sum_j))
                res+=preSum.get(sum_j);
            preSum.put(sum,preSum.getOrDefault(sum,0)+1);
        }
        return res;
    }


    /*===========================================================================================================================
     * 差分数组 1109. 航班预订统计
     * 这里有 n 个航班，它们分别从 1 到 n 进行编号。
     * 有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
     * 请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。
     * */
    //差分数组
    class Difference {
        // 差分数组
        private int[] diff;

        public Difference(int[] nums) {
            assert nums.length > 0;
            diff = new int[nums.length];
            // 构造差分数组
            diff[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                diff[i] = nums[i] - nums[i - 1];
            }
        }

        /* 给闭区间 [i,j] 增加 val（可以是负数）*/
        public void increment(int i, int j, int val) {
            diff[i] += val;
            //当j+1 >= diff.length时，说明是对nums[i]及以后的整个数组都进行修改，那么就不需要再给diff数组减val了。
            if (j + 1 < diff.length) {
                diff[j + 1] -= val;
            }
        }

        public int[] result() {
            int[] res = new int[diff.length];
            // 根据差分数组构造结果数组
            res[0] = diff[0];
            for (int i = 1; i < diff.length; i++) {
                res[i] = res[i - 1] + diff[i];
            }
            return res;
        }
    }
    public int[] corpFlightBookings1(int[][] bookings, int n) {
        int[] nums=new int[n];
        Difference difference=new Difference(nums);
        for (int[] booking:bookings) {
            // 注意转成数组索引要减一哦
            int i = booking[0] - 1;
            int j = booking[1] - 1;
            int val = booking[2];
            difference.increment(i,j,val);
        }
        return difference.result();
    }

    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] nums=new int[n];
        //差分数组初始全部为0
        int[] diff=new int[n];
        for (int[] b:bookings) {
            //下标从0开始
            int firsti=b[0]-1;
            int lasti=b[1]-1;
            int seatsi=b[2];
            //对nums的区间firsti到lasti全部加上seatsi，相当于在diff[firsti]+=seatsi,diff[lasti]-=seatsi
            diff[firsti]+=seatsi;
            if (lasti+1<n){
                diff[lasti+1]-=seatsi;
            }
        }
        //通过diff数组构造原本的nums数组
        nums[0]=diff[0];
        for (int i = 1; i < n; i++) {
            nums[i]=nums[i-1]+diff[i];
        }
        return nums;
    }



    /*===========================================================================================================================
     * 双指针 167. 两数之和 II - 输入有序数组
     * 给定一个已按照 非递减顺序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
     * 函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
     * */
    public int[] twoSum(int[] numbers, int target) {
        int left=0,right=numbers.length-1;
        while (left<right){
            int sum=numbers[left]+numbers[right];
            if (sum==target){
                // 题目要求的索引是从 1 开始的
                return new int[]{left+1,right+1};
            }else if (sum<target){
                left++;
            }else if (sum>target){
                right--;
            }
        }
        return new int[]{-1,-1};
    }

    /* ===========================================================================================================================
    * 1. 两数之和：
    * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
    * 使用map
    * */
    public int[] twoSum1(int[] nums, int target) {
        int n=nums.length;
        HashMap<Integer,Integer> map=new HashMap<>();
        //将nums中的元素放入map中，map<nums[i],i>

        int[] res=new int[2];
        for (int i = 0; i < n; i++) {
            if (map.containsKey(target-nums[i])&&map.get(target-nums[i])!=i){
                res[0]=i;
                res[1]=map.get(target-nums[i]);
                return res;
            }
            map.put(nums[i],i);
        }
        return res;
    }


    /*===========================================================================================================================
     * 双指针 344. 反转字符串
     * 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
     * */
    public void reverseString(char[] s) {
        int left=0;
        int right=s.length-1;
        while (left<right){
            char temp=s[left];
            s[left]=s[right];
            s[right]=temp;
            left++;right--;
        }
    }


    /*===========================================================================================================================
     *二分搜索1 704. 二分查找
     * */
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; // 注意

        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1; // 注意
            else if (nums[mid] > target)
                right = mid - 1; // 注意
        }
        return -1;
    }

    /*===========================================================================================================================
     *二分搜索2 34. 在排序数组中查找元素的第一个和最后一个位置
     * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
     * */
    public int[] searchRange(int[] nums, int target) {
        int[] res=new int[2];
        res[0]=left_bound(nums,target);
        res[1]=right_bound(nums,target);
        return res;
    }
    int left_bound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 别返回，锁定左侧边界
                right = mid - 1;
            }
        }
        // 最后要检查 left 越界的情况
        if (left >= nums.length || nums[left] != target)
            return -1;
        return left;
    }

    int right_bound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 别返回，锁定右侧边界
                left = mid + 1;
            }
        }
        // 最后要检查 right 越界的情况
        if (right < 0 || nums[right] != target)
            return -1;
        return right;
    }


    /*===========================================================================================================================
     *二分搜索3 875. 爱吃香蕉的珂珂
     * 这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。
     * 每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。  
     * 珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。
     * */
    //自变量x=吃香蕉的速度k
    //f(x) 函数就可以这样定义：若吃香蕉的速度为 x 根/小时，则需要 f(x) 小时吃完所有香蕉。
    //target 就很明显了，吃香蕉的时间限制 H 自然就是 target，是对 f(x) 返回值的最大约束。
    int f875(int[] piles,int x){
        int h=0;
        for (int i = 0; i < piles.length; i++) {
            h+=piles[i]/x;
            if (piles[i]%x>0){
                h++;
            }
        }
        return h;
    }
    public int minEatingSpeed(int[] piles, int h) {
        int letf=1; //最小速度为1
        int right=1000000000 + 1;   //最大速度应该是piles的最大值
        while (letf<right){
            int mid=letf+(right-letf)/2;
            if (f875(piles,mid)==h){
                right=mid;
            }else if (f875(piles,mid)>h){
                //花费时间超过了，需要加快速度
                letf=mid+1;
            }else if (f875(piles,mid)<h){
                right=mid;
            }
        }
        return letf;
    }

    /*===========================================================================================================================
     *二分搜索4 1011. 在 D 天内送达包裹的能力
     * 传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
     * 返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。
     * */
    //船的运载能力就是自变量 x。
    //f(x)定义：当运载能力为 x 时，需要 f(x) 天运完所有货物
    //target是运货天数的限制
    int f1011(int[] weights,int x){
        int day=0;
        for (int i = 0; i < weights.length; ) {
            int cap=x;
            while (i<weights.length){
                if (cap<weights[i]){
                    break;
                }else {
                    cap-=weights[i];
                    i++;
                }
            }
            day++;
        }
        return day;
    }
    public int shipWithinDays(int[] weights, int days) {
        int left=0,right=1;

        for (int i = 0; i < weights.length; i++) {
            //最小值是重量中的最大值，这样才能一定吧货物运完
            left=Math.max(weights[i],left);
            //最大值是所有重量和
            right+=weights[i];
        }
        while (left<right){
            int mid=left+(right-left)/2;
            if (f1011(weights,mid)==days){
                right=mid;
            }else if (f1011(weights,mid)<days){
                right=mid;
            }else if (f1011(weights,mid)>days){
                left=mid+1;
            }
        }
        return left;
    }



    /*===========================================================================================================================
     *二分搜索5  410. 分割数组的最大值
     * 给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
     * 对于将数组分成m个子数组有很多方案，在这些方案中找到子数组和最大值最小的
     * */
    // 在每个子数组和不超过 max 的条件下，计算 nums 至少可以分割成几个子数组
    int split(int[] nums,int max){
        //记录最少可以分割的子数组数量，最少是1个部分割
        int count=1;
        int sum=0;
        for (int i = 0; i < nums.length; i++) {
            if (sum+nums[i]>max){
                count++;
                sum=nums[i];
            }else {
                sum+=nums[i];
            }
        }
        return count;
    }
    public int splitArray(int[] nums, int m) {
        int left=nums[0],right=0;
        for (int i = 0; i < nums.length; i++) {
            left=Math.max(nums[i],left);
            right+=nums[i];
        }
        //可能存在多个 max 使得 split(nums, max) 算出相同的 n，因为我们的算法会返回最小的那个 max，所以应该使用搜索左侧边界的二分查找算法。
        //问题变为：在闭区间 [left, right] 中搜索一个最小的 max，使得 split(nums, max) 恰好等于 m。
        while (left<right){
            int mid=left+(right-left)/2;
            int n=split(nums,mid);
            if (n==m){
                right=mid;
            }else if (n<m){
                //划分的子数组数量少了，最大和限制大量，减小
                right=mid;
            }else if (n>m){
                left=mid+1;
            }
        }
/*        for (int max = left; max <=right ; max++) {
            // 如果最大子数组和是 max，
            // 至少可以把 nums 分割成 n 个子数组
            int n=split(nums,max);
            if (n<=m){
                return max;
            }
        }*/
        return left;
    }


    /*===========================================================================================================================
    * 870. 优势洗牌
    * 给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。返回 A 的任意排列，使其相对于 B 的优势最大化。
    * */
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n=nums1.length;
        //将nums2按照降序放入优先队列中，需要存放数字和下标的对应
        PriorityQueue<int[]> priorityQueue=new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1]-o1[1];
            }
        });
        for (int i = 0; i < n; i++) {
            priorityQueue.add(new int[]{i,nums2[i]});
        }
        //nums1是升序排列
        Arrays.sort(nums1);
        int left=0,right=n-1;
        int[] res=new int[n];
        while (!priorityQueue.isEmpty()){
            int[] p=priorityQueue.poll();
            int i=p[0],val=p[1];
            if (val<nums1[right]){
                //可以获得优势
                res[i]=nums1[right];
                right--;
            }else {
                //用最小值来对应nums2中的较大值
                res[i]=nums1[left];
                left++;
            }
        }
        return res;
    }


    /*===========================================================================================================================
    * 316. 去除重复字母  1081. 不同字符的最小子序列
    * 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
    * 要求一、要去重。
    * 要求二、去重字符串中的字符顺序不能打乱s中字符出现的相对顺序。
    * 要求三、在所有符合上一条要求的去重字符串中，字典序最小的作为最终结果。---需要把字典序在前的放在前面，但是又要保证相对顺序
    * */
    public String removeDuplicateLetters(String s) {
        Stack<Character> stack=new Stack<>();
        //维护一个计数器，记录每个字符之后会出现的次数，初始为每个字符的数量
        int[] count=new int[256];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i)]++;
        }
        //boolen数组记录某个字符是否在之前出现过
        boolean[] inStack=new boolean[256];
        for (char c:s.toCharArray()) {
            count[c]--;  //计数器减一
            //用于去重，之前在stack中的元素直接跳过
            if (inStack[c]) continue;
            //将比c大的栈中元素按顺序取出，将c放入
            while (!stack.isEmpty()&&stack.peek()>c){
                if (count[stack.peek()]==0){
                    //栈顶元素在之后的s中不会再出现，不能pop出来，需要用于保持相对顺序
                    break;
                }
                //将栈顶pop出来，并且将栈中是否存在修改
                inStack[stack.pop()]=false;
            }
            stack.push(c);
            inStack[c]=true;
        }
        StringBuffer sb=new StringBuffer();
        while (!stack.isEmpty()){
            sb.append(stack.pop());
        }
        //栈中顺序是反转的
        return sb.reverse().toString();
    }


    /*===========================================================================================================================
    * 26. 删除有序数组中的重复项
    * 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
    * */
    public int removeDuplicates1(int[] nums) {
        int n=nums.length;
        int newind=1;
        for (int i=1;i<n;i++){
            if (nums[i]!=nums[i-1]){
                nums[newind]=nums[i];
                newind++;
            }
        }
        return newind;
    }
    //快慢指针
    public int removeDuplicates(int[] nums) {
        if (nums==null||nums.length==0){
            return 0;
        }
        int left=0;
        for (int i = 1; i <nums.length ; i++) {
            if (nums[left]!=nums[i]){
                nums[++left]=nums[i];
            }
        }
        return ++left;
    }


    /*===========================================================================================================================
     * 27. 移除元素
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
     * 快慢指针：如果 fast 遇到需要去除的元素，则直接跳过，否则就告诉 slow 指针，并让 slow 前进一步。
     * */
    public int removeElement(int[] nums, int val) {
        int fast=0,slow=0;
        while (fast<nums.length){
            if (nums[fast]!=val){
                //先给 nums[slow] 赋值然后再给 slow++，这样可以保证 nums[0..slow-1] 是不包含值为 val 的元素的，最后的结果数组长度就是 slow。
                nums[slow]=nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }



    /*===========================================================================================================================
     * 283. 移动零
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * 把非0的往前挪，挪完之后，后面的就都是0了，然后在用0覆盖后面的。
     * */
    public void moveZeroes(int[] nums) {
        int n=nums.length;
        if (n==0){
            return;
        }
        int index=0;
        for (int i = 0; i < n; i++) {
            if (nums[i]!=0){
                nums[index++]=nums[i];
            }
        }
        while (index<n){
            nums[index++]=0;
        }
    }



    /*===========================================================================================================================
    买卖股票的最佳时机 II
    */
    //1.直接求出相邻两个元素之间的差，将所有正的差值相加即可
    public int maxProfit1(int[] prices) {
        int n=prices.length;
        int res=0;
        for (int i = 1; i <n; i++) {
            int pro=prices[i]-prices[i-1];
            if (pro>0){
                res+=pro;
            }
        }
        return res;
    }
    //2.动态规划：dp[i][0]表示第i天交易完之后手里没有股票的最大利润，dp[i][1]表示第i天交易完之后手里持有股票的最大利润
    //dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
    //dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
    public int maxProfit(int[] prices) {
        int n=prices.length;
        if (prices==null||n==0)
            return 0;

        int[][] dp=new int[n][2];
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        for (int i = 1; i <n ; i++) {
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        //最后一天肯定是手里没有股票的时候，利润才会最大，
        //只需要返回dp[length - 1][0]即可
        return dp[n-1][0];
    }


    /*===========================================================================================================================
    旋转数组
     */
    //1.使用临时数组
    public void rotate1(int[] nums, int k) {
        int n=nums.length;
        int[] nums1=new int[n];
        for (int i = 0; i <n ; i++) {
            nums1[i]=nums[i];
        }
        for (int i=0;i<n;i++){
            int index=(i+k)%n;
            nums[index]=nums1[i];
        }
    }
    //2.多次反转（不需要额外数组空间）
    public void reverse(int[] nums,int l,int r){
        while (l<r){
            int t=nums[l];
            nums[l++]=nums[r];
            nums[r--]=t;
        }
    }
    public void rotate(int[] nums, int k) {
        int n=nums.length;
        k%=n;
        //先反转前k个
        reverse(nums,0,n-k-1);
        //反转后k个
        reverse(nums,n-k,n-1);
        //反转整体
        reverse(nums,0,n-1);
    }


    /*===========================================================================================================================
     * 存在重复元素
     * */
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i=1;i<nums.length;i++){
            if (nums[i]==nums[i-1])
                return true;
        }
        return false;
    }


    /*===========================================================================================================================
     * 只出现一次的数字
     * 使用异或操作
     * */
    public int singleNumber(int[] nums) {
        int res=0;
        for (int num:nums) {
            res^=num;
        }
        return res;
    }


    /*===========================================================================================================================
     * 两个数组的交集 II
     * 1.排序后，双指针
     * */
    public int[] intersect1(int[] nums1, int[] nums2) {
        int n1=nums1.length;
        int n2=nums2.length;
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        ArrayList<Integer> res=new ArrayList<>();
        int i=0,j=0;
        //int index=0;
        while (i<n1&&j<n2){
            if (nums1[i]==nums2[j]){
                res.add(nums1[i]);
                i++;j++;
                //index++;
            }else if (nums1[i]<nums2[j]){
                i++;
            }else {
                j++;
            }
        }
        int m=res.size();
        System.out.println("m="+m);
        System.out.println(res.toString());
        int[] r=new int[m];
        for (int k = 0; k < m; k++) {
            r[k]=res.get(k);
        }
        return r;
    }
    //2.使用map:遍历nums1中的所有元素，把它存放到map中，其中key就是nums1中的元素，value就是这个元素在数组nums1中出现的次数。
    //遍历nums2中的所有元素，查看map中是否包含nums2的元素，如果包含，就把当前值加入到集合list中，然后对应的value要减1。
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer,Integer> map=new HashMap<>();
        ArrayList<Integer> list=new ArrayList<>();
        for (int num:nums1) {
            map.put(num,map.getOrDefault(num,0)+1);
        }
        for (int num:nums2) {
            if (map.getOrDefault(num,0)>0){
                list.add(num);
                map.put(num,map.get(num)-1);
            }
        }
        int m=list.size();
        int[] r=new int[m];
        for (int k = 0; k < m; k++) {
            r[k]=list.get(k);
        }
        return r;

    }


    /*===========================================================================================================================
     * 加一
     * */
    public int[] plusOne(int[] digits) {
        int n=digits.length;
        System.out.println("n="+n);
        for (int i = n-1; i >=0; i--) {
            if (digits[i]==9){
                //如果数组当前元素等于9，那么加1之后
                //肯定会变为0，我们先让他变为0
                digits[i]=0;
            }else {
                //如果数组当前元素不等于9，直接加1
                //然后直接返回
                digits[i]++;
                //System.out.println(digits[i]);
                return digits;
            }
        }
        //如果所有元素都为9
        int[] res=new int[n+1];
        res[0]=1;
        return res;
    }





    /*===========================================================================================================================
     * 有效的数独
     * */
    public boolean isValidSudoku(char[][] board) {
        int n=board.length;
        int[][] line=new int[n][n];
        int[][] column=new int[n][n];
        int[][] cell=new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j]=='.'){
                    continue;
                }
                int now=board[i][j]-'0'-1;
                int k=i/3*3+j/3;
                if (line[i][now]!=0||column[j][now]!=0||cell[k][now]!=0)
                    return false;
                line[i][now]=column[j][now]=cell[k][now]=1;
            }
        }
        return true;
    }


    /*===========================================================================================================================
     *旋转图像
     * 先上下交换，再对角线交换
     * */
    public void rotate(int[][] matrix) {
        int n=matrix.length;
        for (int i = 0; i < n/2; i++) {
            int[] temp=matrix[i];
            matrix[i]=matrix[n-i-1];
            matrix[n-i-1]=temp;
        }
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                int temp=matrix[i][j];
                matrix[i][j]=matrix[j][i];
                matrix[j][i]=temp;
            }
        }
    }





    public static void main(String[] args) {
//        int[] nums1=new int[]{3,2,4};
//        int[] nums2=new int[]{2,2};

        // String columnTitle = "AB";

        Solution_1array object=new Solution_1array();

        //int res=object.removeDuplicates(nums1);
        //int res=object.maxProfit(nums1);
        //object.rotate(nums1,3);
        //System.out.println(object.containsDuplicate(nums1));
        //System.out.println(object.singleNumber(nums1));
//        int[] res=object.intersect(nums1,nums2);
        //int[] res=object.plusOne(nums1);
        //object.moveZeroes(nums1);
//        int[] res=object.twoSum(nums1,6);
//        System.out.println(object.isValidSudoku(times));


        //System.out.println(res);
        /*for (int i = 0; i < res.length; i++) {
            System.out.println(res[i]);
        }*/
/*        for (int r:nums1) {
            System.out.println(r);
        }*/

    }
}
